#-*- coding: utf-8 -*-
import random
import cpu

#FONCTIONS AJOUTÉES

def tri_bulles(t):
	stop = False
	while not stop:
		stop = True
		for i in range(len(t)-1):
			if t[i] > t[i+1]:
				t[i], t[i+1] = t[i+1], t[i]
				stop = False
def bubble_sort(t):
	tri_bulles(t)

#SUITE ORIGINALE.

def python_sort(t):
    t.sort()

def insertion_sort(t):
    n = len(t)
    for i in range(1,n):
        clef = t[i]
        j = i - 1
        while j >= 0 and t[j] > clef:
            t[j+1] = t[j]
            j = j - 1
        t[j+1] = clef

def selection_sort(t):
    n = len(t)
    for i in range(n-1):
        small = i
        for j in range(i+1,n):
            if t[j] < t[small]:
                small = j
        (t[i], t[small]) = (t[small], t[i])

def merge_sort(t): # permet d'avoir une interface in place, similaire aux autres tris
    t = merge_sort_notinplace(t)

def merge_sort_notinplace(t):
    n = len(t)
    if n > 1:
        (t1, t2) = split(t)
        t1 = merge_sort_notinplace(t1)
        t2 = merge_sort_notinplace(t2)
        return merge(t1, t2)
    else:
        return t

def split(t):
    """ precondition: len(t) >= 2 """
    mid = len(t) / 2
    t1 = t[:mid]
    t2 = t[mid:]
    return (t1, t2)

def merge(t1, t2):
    if len(t1) == 0:
        return t2
    elif len(t2) == 0:
        return t1
    elif t1[0] < t2[0]:
        return [t1[0]] + merge(t1[1:], t2)
    else:
        return [t2[0]] + merge(t1, t2[1:])

def dicho_search(t, x):
    start = 0
    end = len(t) - 1
    mid = start + (end - start) / 2
    while (end - start > 0) and x != t[mid]:
        if x < t[mid]:
            end = mid - 1
        else:
            start = mid + 1
        mid = start + (end - start) / 2
    if len(t) > 0 and x == t[mid]:
        return mid
    else:
        return None

def test(n):
    t1 = range(n)
    t2 = range(n,0,-1)
    t3 = []
    for i in range(n):
        t3.append(random.randint(0,n))
    print '%6d ' % n,
    print '%7.2f' % (cpu.cpuTime('selection_sort', 'sort', str(t1), 10) * 1000),
    print '%7.2f' % (cpu.cpuTime('insertion_sort', 'sort', str(t1), 10) * 1000),
    print '%7.2f' % (cpu.cpuTime('merge_sort', 'sort', str(t1), 10) * 1000),
    print '    %7.2f' % (cpu.cpuTime('selection_sort', 'sort', str(t2), 10) * 1000),
    print '%7.2f' % (cpu.cpuTime('insertion_sort', 'sort', str(t2), 10) * 1000),
    print '%7.2f' % (cpu.cpuTime('merge_sort', 'sort', str(t2), 10) * 1000),
    print '    %7.2f' % (cpu.cpuTime('selection_sort', 'sort', str(t3), 10) * 1000),
    print '%7.2f' % (cpu.cpuTime('insertion_sort', 'sort', str(t3), 10) * 1000),
    print '%7.2f' % (cpu.cpuTime('merge_sort', 'sort', str(t3), 10) * 1000)

if __name__ == '__main__':
    print "Temps affiches en msec"
    print 'n      t1: sel     ins     mer     t2: sel     ins     mer     t3: sel     ins     mer'
    for i in range(100, 901, 100):
        test(i)
